package com.ztom.dp;

/**
 * 使用最小花费爬楼梯
 * <p>
 * https://leetcode-cn.com/problems/min-cost-climbing-stairs/
 *
 * @author ZhangTao
 */
public class Code04MinCostClimbingStairs {

    public int minCostClimbingStairs2(int[] cost) {
        if (cost == null || cost.length == 0) {
            return -1;
        }

        return process(cost, cost.length);
    }

    private int process(int[] cost, int n) {
        // 选择前两个台阶出发
        if (n == 0 || n == 1) {
            return 0;
        }

        // 当前台阶可以由前一个或前两个台阶到达, 取最小值
        int p1 = process(cost, n - 1) + cost[n - 1];
        int p2 = process(cost, n - 2) + cost[n - 2];

        return Math.min(p1, p2);
    }

    public int minCostClimbingStairs1(int[] cost) {
        if (cost == null || cost.length == 0) {
            return -1;
        }
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[n];
    }

    public int minCostClimbingStairs(int[] cost) {
        if (cost == null || cost.length == 0) {
            return -1;
        }
        int n = cost.length;
        int prepre = 0;
        int pre = 0;
        int res = 0;
        for (int i = 2; i <= n; i++) {
            res = Math.min(pre + cost[i - 1], prepre + cost[i - 2]);
            prepre = pre;
            pre = res;
        }

        return res;
    }
}
